/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.lang;

import java.lang.ref.*;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;

/**
 * 这个类提供线程局部变量。这些变量与普通变量的不同之处在于， 每个访问这些变量的线程(通过其get或set方法)都有自己独立初始化的变量副本。
 * ThreadLocal实例通常是类中的私有字段，它们希望将状态与线程(例如，用户ID或事务ID)关联起来。
 * 
 * <p>
 * ThreadLocal看类名就是线程本地变量的意思。从使用上来说，如果定义了一个ThreadLocal，那么各个线程针对这个ThreadLocal进行get/set都是线程独立的，也就是说，是线程隔离的本地变量。
 * 从实现上来说，每个线程在运行过程中都可以通过Thread.currentThread()获得与之对应的Thread对象，
 * 而每个Thread对象都有一个ThreadLocalMap类型的成员，ThreadLocalMap是一种hashmap，它以ThreadLocal作为key。
 * 所以，通过Thread对象和ThreadLocal对象二者，才可以唯一确定到一个value上去。线程隔离的关键，正是因为这种对应关系用到了Thread对象。
 *
 * <p>
 * 例如，下面的类生成每个线程的唯一标识符。 线程的id在它第一次调用ThreadId.get()时被分配，并且在以后的调用中保持不变。
 * 
 * threadId这个你定义的ThreadLocal对象，它是当作key使用的，而它的初始的value则在initialValue中给出。
 * 各个线程第一次get时会调用到重写的initialValue函数，由于AtomicInteger利用了volatile+CAS，
 * 所以各个线程调用get时不需要同步操作（调用get，最终会间接调用到initialValue）。
 * 
 * 即每个线程都能通过threadId这个ThreadLocal对象，获得一个唯一的线程ID。
 * threadId这个ThreadLocal对象被设置为了一个静态对象，这就让整个内存中只有这一个对象。
 * ThreadLocal给多个线程作为key来使用，自然只保持同一个对象才是正确的选择。
 * 
 * <pre>
 * import java.util.concurrent.atomic.AtomicInteger;
 *
 * public class ThreadId {
 * 	// 原子整数，包含下一个要分配的线程ID
 * 	private static final AtomicInteger nextId = new AtomicInteger(0);
 *
 * 	// 包含每个线程ID的线程局部变量
 * 	private static final ThreadLocal&lt;Integer&gt; threadId = new ThreadLocal&lt;Integer&gt;() {
 * 		&#64;Override
 * 		protected Integer initialValue() {
 * 			return nextId.getAndIncrement();
 * 		}
 * 	};
 *
 * 	// 返回当前线程的唯一ID，并在必要时将其赋值
 * 	public static int get() {
 * 		return threadId.get();
 * 	}
 * }
 * </pre>
 * <p>
 * 只要线程是活的并且ThreadLocalinstance是可访问的，那么每个线程都拥有一个对thread-local变量副本的隐式引用;
 * 当一个线程消失后，它的所有线程本地实例副本都将被垃圾收集(除非存在对这些副本的其他引用)。
 * 
 * 泛型T规定了ThreadLocal对象的对应的value的类型。
 *
 * @author Josh Bloch and Doug Lea
 * @since 1.2
 */
public class ThreadLocal<T> {
	/**
	 * 每个ThreadLocal对象是需要在ThreadLocalMaps里作为key，而ThreadLocalMaps也是一种hashmap，所以ThreadLocal对象需要有哈希值。
	 * 
	 * 每个ThreadLocal对象都有一个int值的成员变量，作为它在ThreadLocalMaps里的哈希值。
	 * 
	 * threadlocal依赖于每个线程的线性探测散列映射(Thread.threadLocals和inheritableThreadLocals)。
	 * ThreadLocal对象充当键，通过threadLocalHashCode进行搜索。
	 * 
	 * 这是一个自定义hashcode(仅在ThreadLocalMaps中有用)，
	 * 它在相同线程连续构造threadlocals被使用的常见情况下消除了冲突，而在不常见的情况下保持良好的行为。
	 */
	private final int threadLocalHashCode = nextHashCode();

	/**
	 * 要给出的下一个哈希码。自动更新。从0开始。
	 * 
	 * 第一次构造ThreadLocal对象时，它的哈希值为0。 此后，每个新构造出来的ThreadLocal对象都新增一个魔数0x61c88647。
	 * 
	 * 使用了AtomicInteger，就算两个线程同时构造了ThreadLocal对象，也能保证这个int成员变量各自线程的不同。
	 */
	private static AtomicInteger nextHashCode = new AtomicInteger();

	/**
	 * 连续生成的hashcode之前的差---对于两倍大小的幂表，将连续的线程本地id变成近乎最优的扩散乘法哈希值
	 * 
	 * 魔数0x61c88647在2的幂为容量的哈希表上，能够完美散列，没有一个元素会哈希冲突。
	 * 
	 */
	private static final int HASH_INCREMENT = 0x61c88647;

	/**
	 * 返回下一个哈希码。
	 */
	private static int nextHashCode() {
		return nextHashCode.getAndAdd(HASH_INCREMENT);
	}

	/**
	 * 返回当前线程的这个线程局部变量的“初始值”。
	 * 该方法将在线程第一次使用get方法访问变量时被调用，除非线程之前调用了set方法，在这种情况下，将不会为线程调用initialValue方法。
	 * 通常，每个线程最多调用一次这个方法，但在后续调用remove和get的情况下，它可能会被再次调用。
	 *
	 * <p>
	 * 这个实现只是返回null; 如果程序员希望线程局部变量的初始值不是null， 则必须将ThreadLocal子类化，并覆盖该方法。通常，将使用匿名内部类。
	 *
	 * @return the initial value for this thread-local
	 */
	protected T initialValue() {
		return null;
	}

	/**
	 * 创建线程局部变量。变量的初始值是通过调用Supplier的get方法确定的。
	 * 
	 * 可以通过传给withInitial方法一个Supplier接口的子类，来构造得到一个SuppliedThreadLocal对象，它是ThreadLocal的子类。
	 * 相比构造一个匿名内部类，其实这种方式就是把要重写的initialValue方法的逻辑，写在了Supplier接口的子类里。
	 * 相同之处：你自己的匿名内部类和SuppliedThreadLocal，都是ThreadLocal的子类，只是SuppliedThreadLocal这个类有个名字而已。
	 * 
	 * 注意方法签名为<S> ThreadLocal<S> withInitial(Supplier<? extends S>
	 * supplier)，形参为泛型的通配符，所以可以写出下面这种代码。
	 * 
	 * //只要Supplier的实际泛型类型，是赋值过去的泛型类型的子类，就可以 ThreadLocal<Number> localNumber =
	 * ThreadLocal.withInitial(new Supplier<Integer>() {
	 * 
	 * @Override public Integer get() { return null; }; });
	 *
	 * @param <S>      the type of the thread local's value
	 * @param supplier the supplier to be used to determine the initial value
	 * @return a new thread local variable
	 * @throws NullPointerException if the specified supplier is null
	 * @since 1.8
	 */
	public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
		return new SuppliedThreadLocal<>(supplier);
	}

	/**
	 * 创建线程局部变量。
	 * 
	 * @see #withInitial(java.util.function.Supplier)
	 */
	public ThreadLocal() {
	}

	/**
	 * 返回当前线程中这个线程局部变量的的值。 如果该变量对于当前线程没有值，则首先将其初始化为调用initialValue方法返回的值。
	 *
	 * @return the current thread's value of this thread-local
	 */
	public T get() {
		// 刚开始就直接找到了调用当前函数的线程是哪个（Thread t = Thread.currentThread();），
		// 然后调用getMap，最后居然直接去取Thread对象的一个ThreadLocal.ThreadLocalMap类型的threadLocals成员.
		// 上面这点就直接解释了，为什么ThreadLocal可以实现线程隔离的线程私有变量。
		// 因为它把这个Map对象直接作为了Thread对象的成员，这样，每个运行的线程都对应到一个唯一的Thread对象，
		// 而每个Thread对象都保存着各自的ThreadLocal.ThreadLocalMap类型的成员变量。
		Thread t = Thread.currentThread();
		ThreadLocalMap map = getMap(t); // return t.threadLocals;
		if (map != null) {
			// 如果当前线程的Thread对象已经创建了ThreadLocal.ThreadLocalMap类型的成员变量：
			// 直接调用getEntry(ThreadLocal对象)，通过key获得了key所在的entry（entry自然包含了key和key对应的value）。
			// 如果这个entry对象不为空，获得entry的value，返回value。
			// 如果这个entry对象为空，还是会调用到setInitialValue去。
			ThreadLocalMap.Entry e = map.getEntry(this);
			if (e != null) {
				@SuppressWarnings("unchecked")
				T result = (T) e.value;
				return result;
			}
		}
		// 如果当前线程的Thread对象还没有创建ThreadLocal.ThreadLocalMap类型的成员变量：
		// get函数中，调用getMap将会返回null。紧接着，会调用setInitialValue函数。
		// setInitialValue函数里，通过initialValue获得初值。然后调用getMap又将会返回null，进else分支调用createMap：
		// 果然，创建了一个ThreadLocal.ThreadLocalMap对象赋值给了Thread对象的成员变量。
		return setInitialValue();
	}

	/**
	 * set()的变体，以建立initialValue。用于在用户覆盖set()方法时代替set()。
	 *
	 * @return the initial value
	 */
	private T setInitialValue() {
		T value = initialValue();
		Thread t = Thread.currentThread();
		ThreadLocalMap map = getMap(t);
		if (map != null)
			// 如果map对象存在，直接set值
			map.set(this, value);
		else// 如果map对象不存在，用第一对键值对，创建map
			createMap(t, value);
		return value;
	}

	/**
	 * 将当前线程的这个线程局部变量的副本设置为指定的值。 大多数子类将不需要重写这个方法，仅仅依靠initialvalue方法来设置线程局部变量的值。
	 *
	 * @param value the value to be stored in the current thread's copy of this
	 *              thread-local.
	 */
	public void set(T value) {
		Thread t = Thread.currentThread();
		ThreadLocalMap map = getMap(t);
		if (map != null)
			map.set(this, value);
		else
			createMap(t, value);
	}

	/**
	 * 为这个线程本地变量删除当前线程的值。 如果这个线程局部变量随后被当前线程读取，它的值将通过
	 * 调用它的initialValue方法进行初始化，除非它的值是由当前线程在过渡期间设置的。 这可能导致在当前线程中多次调用initialValue方法。
	 *
	 * @since 1.5
	 */
	public void remove() {
		ThreadLocalMap m = getMap(Thread.currentThread());
		if (m != null)
			m.remove(this);
	}

	/**
	 * 获取与ThreadLocal关联的映射。覆盖了inInheritableThreadLocal。
	 *
	 * @param t the current thread
	 * @return the map
	 */
	ThreadLocalMap getMap(Thread t) {
		return t.threadLocals;
	}

	/**
	 * 创建与ThreadLocal相关联的映射。inInheritableThreadLocal覆盖。
	 *
	 * @param t          the current thread
	 * @param firstValue value for the initial entry of the map
	 */
	void createMap(Thread t, T firstValue) {
		// 这个Map的第一个键值对：key为this即ThreadLocal对象，value为T对象。
		// 其实看到这里，就能理解到ThreadLocal的基本原理了：
		// 每个线程对应到一个Map对象上去，且key的类型为ThreadLocal。而且根据前面ThreadLocal的哈希值成员的讲解，
		// 可以得知，每个ThreadLocal对象的哈希值肯定不同，所以，当不同线程想要根据同一个key来get/set
		// value时，必须复用ThreadLocal对象
		// （也就是为什么ThreadLocal对象一般设置为static的原因，比如那个来自API文档的标准示例。）。
		t.threadLocals = new ThreadLocalMap(this, firstValue);
	}

	/**
	 * 工厂方法来创建继承的线程局部变量的映射。 设计为仅从线程构造函数调用。
	 * 
	 * 工厂方法，当父线程创建子线程，通过此方法构造出一个ThreadLocalMap赋值给 子线程的inheritableThreadLocals成员。
	 * 这个方法是父线程通过new Thread间接调用到的。
	 *
	 * @param parentMap the map associated with parent thread
	 * @return a map containing the parent's inheritable bindings
	 */
	static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
		return new ThreadLocalMap(parentMap);
	}

	/**
	 * 方法childValue在子类InheritableThreadLocal中明显定义，但在这里内部定义，
	 * 以便提供createInheritedMap工厂方法，而不需要继承InheritableThreadLocal中的map类。
	 * 这种技术比在方法中嵌入instanceof测试更可取。
	 * 
	 * 默认实现是抛异常，InheritableThreadLocal子类实现了此方法，逻辑可为： 可根据父线程的value来设置子线程的value。
	 */
	T childValue(T parentValue) {
		throw new UnsupportedOperationException();
	}

	/**
	 * ThreadLocal的扩展，它从指定的提供者获得初始值。
	 */
	static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {

		private final Supplier<? extends T> supplier;

		SuppliedThreadLocal(Supplier<? extends T> supplier) {
			this.supplier = Objects.requireNonNull(supplier);
		}

		@Override
		protected T initialValue() {
			return supplier.get();
		}
	}

	/**
	 * ThreadLocalMap是一个定制的哈希映射，只适合维护线程本地值。
	 * 在ThreadLocal类之外不导出任何操作。这个类是包私有的，允许在类Thread中声明字段。
	 * 为了帮助处理非常大且长期存在的使用，哈希表条目使用weakreferences作为键。
	 * 但是，由于引用队列没有被使用，所以只有当表开始用完空间时，陈旧的条目才会被删除。
	 */
	static class ThreadLocalMap {

		/**
		 * 这个哈希映射中的条目扩展了WeakReference，使用它的主ref字段作为键(它总是threadlocal对象)。
		 * 请注意，空键(即entry.get()== null)意味着键不再被引用，所以条目可以从表中删除。 在下面的代码中，这样的条目被称为“陈旧条目”。
		 * 
		 * 继承了WeakReference，而尖括号里面的ThreadLocal<?>指定了父类的referent成员的类型。
		 * 这里，把这个referent成员，作为了entry的key使用。 Reference 里面有 private T referent;
		 * 
		 * 自己新加了一个value成员，作为了entry的value使用。
		 * 继承使用WeakReference的父类成员referent，当没有强引用指向referent这个对象时，可能这个referent会被回收。
		 * 从下面测试类可以看到，当执行gc时，没有强引用的weak对象被回收。
		 * 由于ThreadLocal对象一般设置为static，那么只有当这个静态变量赋值为null时，entry的父类成员referent才可能被回收。
		 */
		static class Entry extends WeakReference<ThreadLocal<?>> {
			/** 与这个ThreadLocal相关联的值。 */
			Object value;

			Entry(ThreadLocal<?> k, Object v) {
				super(k);
				value = v;
			}
		}

		/*
		 * import java.lang.ref.WeakReference;
		 * 
		 * public class WeakReferenceDemo { static class Entry extends
		 * WeakReference<String> { String member;
		 * 
		 * public Entry(String referent, String member) { super(referent); this.member =
		 * member; } } static Entry entry;
		 * 
		 * static void test () { String Weak = new String("weak"); String Member = new
		 * String("member"); entry = new Entry(Weak,Member);
		 * 
		 * System.gc(); System.out.println("进行gc时，Reference类的referent成员有强引用，member有强引用："
		 * + entry.get());
		 * 
		 * Weak = null; System.gc();
		 * System.out.println("进行gc时，Reference类的referent成员没有强引用，member有强引用：" +
		 * entry.get()); }
		 * 
		 * public static void main(String[] args) { test(); } }打印结果：
		 * 进行gc时，Reference类的referent成员有强引用，member有强引用：weak
		 * 进行gc时，Reference类的referent成员没有强引用，member有强引用：null
		 * 
		 * 
		 * /** 初始容量，必须是2的幂。
		 */
		private static final int INITIAL_CAPACITY = 16;

		/**
		 * 表，根据需要调整大小。长度必须是2的幂。
		 * 
		 * 由于开放寻址用的是nextIndex来寻找下一个可能位置，所以Entry[] table实际是一个环形数组。在寻找位置过程中，如果到达了len，那么跳转到0。
		 * 
		 */
		private Entry[] table;

		/**
		 * 表中的条目数。
		 */
		private int size = 0;

		/**
		 * 要调整大小的下一个大小值。
		 */
		private int threshold; // Default to 0

		/**
		 * 设置调整大小阈值，以维持最坏的2/3负载系数。
		 */
		private void setThreshold(int len) {
			threshold = len * 2 / 3;
		}

		/**
		 * 增量i对len取模。
		 * 
		 * 最重要是nextIndex，它是key放入map中，如果发生了哈希冲突，寻找下一个可能位置时，将使用的函数。
		 * nextIndex和prevIndex的逻辑很简单，只是向后或向前移动索引，超出范围时，就取模容量。
		 */
		private static int nextIndex(int i, int len) {
			return ((i + 1 < len) ? i + 1 : 0);
		}

		/**
		 * 减i对len取模。
		 */
		private static int prevIndex(int i, int len) {
			return ((i - 1 >= 0) ? i - 1 : len - 1);
		}

		/**
		 * 构造一个新映射，初始包含(firstKey, firstValue)。
		 * ThreadLocalMaps是惰性构造的，所以我们只在至少有一个条目要放入时才创建一个。
		 */
		ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
			table = new Entry[INITIAL_CAPACITY];//使用初始容量，作为大小，创建数组
			int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);//哈希值取模，得到数组下标
			table[i] = new Entry(firstKey, firstValue);//刚创建，肯定不冲突。直接赋值即可
			size = 1;
			setThreshold(INITIAL_CAPACITY);
		}

		/**
		 * 构造一个新的映射，包括所有从可继承的ThreadLocals的父映射。仅由createInheritedMap调用。
		 * 
		 * 根据父线程的inheritableThreadLocals字段构造子线程（this）的inheritableThreadLocals。
         * 这个构造器只能被 静态工厂方法createInheritedMap调用
         * 
         * 需要注意的是，父线程的inheritableThreadLocals字段和子线程的inheritableThreadLocals字段，
         * 如果直接使用InheritableThreadLocal的childValue方法，那么它们之间的value只是浅复制。
         * 要想解决这点，需要你继承InheritableThreadLocal并重写childValue方法，在方法内部new新对象出来。
		 *
		 * @param parentMap the map associated with parent thread.
		 */
		private ThreadLocalMap(ThreadLocalMap parentMap) {
			Entry[] parentTable = parentMap.table;
			int len = parentTable.length;
			setThreshold(len);
			table = new Entry[len];

			for (int j = 0; j < len; j++) {
				Entry e = parentTable[j];// 对parentTable进行遍历，得到e
				if (e != null) {
					@SuppressWarnings("unchecked")
					ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
					if (key != null) {
						//判断key，不为null，才说明这是个有效entry
                        //childValue的原实现抛异常，所以key的真正类型肯定是ThreadLocal的子类，以重写该方法
                        //并且重写方法实现，可以根据父线程的value，得到子线程的新value
                        //一般是InheritableThreadLocal的实现，直接返回父线程的value。
						Object value = key.childValue(e.value);
						Entry c = new Entry(key, value);
						int h = key.threadLocalHashCode & (len - 1);
						while (table[h] != null)
							h = nextIndex(h, len);//开放寻址法
                        //最终h为，哈希冲突后的最终位置。如果没有冲突，那么h == j
						table[h] = c;
						size++;
					}
				}
			}
		}

		/**
		 * 获取与key相关联的条目。这个方法本身只处理快速路径: 直接命中已经存在的键。否则它将传递给getEntryAfterMiss。
		 * 这是为了最大化直接命中的性能而设计的，部分原因是使这种方法易于内联。
		 * 
		 * 根据key的hash值获得数组下标，但如果传入key和entry的key
         * 不是同一个对象，那么说明哈希冲突了。
		 *
		 * @param key the thread local object
		 * @return the entry associated with key, or null if no such
		 */
		private Entry getEntry(ThreadLocal<?> key) {
			int i = key.threadLocalHashCode & (table.length - 1);
			Entry e = table[i];
			//只有当entry非null，且key为同一个对象时，才直接返回value
			if (e != null && e.get() == key)
				return e;
			//取模下标无法直接得到，考虑哈希冲突。这里有两种情况：
            //1.e不为null，但e的key与传入key不同
            //2.e为null，调用下面函数将直接返回null。
			//哈希值取模下标的entry没找到，就认为目标key肯定不在map里了。
			//显然，ThreadLocalMap的函数逻辑是保证了这样一点：多个哈希值不同但取模下标相同的ThreadLocal，
			//在你操作完毕后，或者说操作开始前，它们肯定从这个取模下标开始放置的（后面的由于冲突，会依次放在后面索引）。
			else
				return getEntryAfterMiss(key, i, e);
		}
		
		// 一个数组元素为null，称为null entry
		// 一个数组元素虽不为null，但key为null，称为stale entry
		// 循环通常从一个索引向后搜索，直到遇到第一个null entry（一般是指循环处理前，就是null的entry），结束循环。将这个索引直到第一个null entry称为连续段。

		/**
		 * 当键在其直接哈希槽中找不到时使用的getEntry方法的版本。
		 * 
		 * 此方法考虑了传入key，因为哈希冲突，所以取模下标不是其实际所在下标。
         * 通过循环往后移动，如果直到null的entry前，都没有
         * 找到key，那么返回null。
		 *
		 * @param key the thread local object
		 * @param i   the table index for key's hash code
		 * @param e   the entry at table[i]
		 * @return the entry associated with key, or null if no such
		 */
		private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
			Entry[] tab = table;
			int len = tab.length;
			
			//循环，不断寻址以找到那个哈希冲突的key。简而言之，向后搜索连续段
			while (e != null) {//当为null时，循环停止。因为当初因哈希冲突set值时，也是set到第一个不为null的位置
				ThreadLocal<?> k = e.get();//获得当前entry的key
				if (k == key)//第一次循环不可能进入此分支，此后可能。进入说明找到了哈希冲突的位置的entry
					return e;
				
				if (k == null)//寻址的过程中，不巧发现了包含null key的entry
					// expungeStaleEntry的作用：向后搜索连续段，如果遇到stale entry就清空（所以刚开始就会把i下标清空），
					// 如果遇到取模下标不等于实际下标的entry，为其再哈希，以使得它更靠近取模下标，甚至直接到取模下标上去。
					
					// 所以，如果之后的连续段中，有包含key的entry，那么一定移动使得其更加靠近取模下标。
					// 如果有包含key的entry，要么这个entry已经在i下标上了，要么i以及之后N个下标刚好是N+1个取模下标也等于i的entry分布在上面
					//（当然，也有这几个entry没有一个是包含key的entry）。
					
					// 进入这个分支，i 会保持不变（注意，本地循环不会执行i = nextIndex(i, len);）。
					// 如果后面没有一个取模下标也等于i的entry，那么由于expungeStaleEntry的行为，i 下标为null，再执行e = tab[i]，循环直接退出。
					// 这里也很自信，因为expungeStaleEntry也会向后搜索连续段，所以相当于将剩余搜索工作交给了expungeStaleEntry。
					expungeStaleEntry(i);//执行完此函数，i索引的entry不一定变成null
				
				else//利用nextIndex，寻址到冲突后的实际位置
					i = nextIndex(i, len);
				e = tab[i];//将新下标所在entry赋值给e
			}
			//如果考虑了哈希冲突后，开放寻址还是不能找到entry，那么说明该key确实不在map中
			return null;
		}

		/**
		 * 设置与key相关联的值。
		 * 
		 * set会被ThreadLocal的set方法直接调用，如果含有key的entry存在，那么更新value即可；
		 * 否则新建一个entry即可。它可能会有后续调用。
		 *
		 * @param key   the thread local object
		 * @param value the value to be set
		 */
		private void set(ThreadLocal<?> key, Object value) {

			// 我们没有像使用get()那样使用快速路径，因为使用set()创建新条目与
			// 替换现有条目至少是一样常见的，在这种情况下，快速路径往往会失败。

			Entry[] tab = table;
			int len = tab.length;
			int i = key.threadLocalHashCode & (len - 1);
			
			//循环开始，获得i位置的entry
			//当循环停止时，i位置的entry肯定null
			for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {//每次循环后，i使用nextIndex移动i，并赋值e
				ThreadLocal<?> k = e.get();

				if (k == key) {//如果进入if (k == key)分支，说明找到了含有key的entry，更新value即可。
					e.value = value;//设置新的value
					return;
				}

				if (k == null) {//当前循环找到了一个stale entry
					// 如果进入if (k == null)分支，说明只是遇到了一个stale entry，但之后的处理不能再交给自己的剩余循环了，因为自己的循环没有对stale entry进行处理。
					// 显然replaceStaleEntry做了足够的处理，以至于这里都直接返回了。
					
					// 传入参数i ，是为了让replaceStaleEntry，从剩余进度继续搜索下去。
					// 传入参数key和value，是为了replaceStaleEntry可以找到含有key的entry，并在找到的情况下进行value替换。
					// replaceStaleEntry会对搜索过程中遇到的stale entry进行处理的，现在我们对replaceStaleEntry简单理解到这样即可。
					replaceStaleEntry(key, value, i);
					return;
				}
			}
			// 如果循环结束，那么说明确实没有一个 含有key的entry，那么新建一个entry即可。
			tab[i] = new Entry(key, value);
			int sz = ++size;
			//cleanSomeSlots返回真说明有stale entry被清空了，清理掉至少一个，size肯定减小了；
            //只有当 cleanSomeSlots返回假 且到达阈值时，才肯定需要rehash
			if (!cleanSomeSlots(i, sz) && sz >= threshold)
				rehash();
		}

		/**
		 * 删除为key的条目。
		 */
		private void remove(ThreadLocal<?> key) {
			Entry[] tab = table;
			int len = tab.length;
			int i = key.threadLocalHashCode & (len - 1);
			for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {
				if (e.get() == key) {
					e.clear();
					expungeStaleEntry(i);
					return;
				}
			}
		}

		/**
		 * 将set操作期间遇到的陈旧条目替换为指定键的条目。 传入value参数的值将存储在条目中，无论指定的键是否已经存在条目。
		 * 作为一个副作用，该方法将删除“run”中包含陈旧条目的所有陈旧条目。 (run是两个空槽之间的条目序列。)
		 * 
		 * replaceStaleEntry函数中，无论怎样，都会把传入的key和value塞到staleSlot所在的下标上去，只不过有两种情况都会达到这个目标，具体看注释。
		 * 另外，该函数会把staleSlot参数所在的run里的所有stale entry都给清理掉。
		 * run：一个run指给定索引前后延伸的连续段，注意，延伸是考虑到环形数组了的。
		 * 
		 * 总的来说，staleSlot是从set方法里，对应的hash对应得格开始找，得到的，所以属于key的正常逻辑。
		 * 所以，value最后会到staleSlot所在下标中。
		 * 但是value可能在staleSlot后面，如果直接移动到那里，可能会产生空格，导致不连续了。
		 * 所以讲staleSlot和原来的key交换位置，然后从run的开始对stale entry进行清理。
		 * 这样子的清理，一定能处理，交换到原来key位置的stale entry，并且妥善处理之后的entry。
		 *
		 * @param key       the key
		 * @param value     the value to be associated with key
		 * @param staleSlot index of the first stale entry encountered while searching
		 *                  for key.
		 */
		private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {
			
			Entry[] tab = table;
			int len = tab.length;
			Entry e;

			// 定义了一个slotToExpunge，它代表需要从这个索引开始往后清理stale entry（当然，是通过expungeStaleEntry清理的）。初始值为staleSlot。
			// slotToExpunge，它刚开始等于staleSlot。如果最终slotToExpunge不等于staleSlot，那么它的值为 staleSlot所在的run里，最前面的stale entry的所在索引。
			// 同时，关于slotToExpunge还有一个结论：以该函数执行前作为观察标准，staleSlot所在的run里，
			// 如果除了参数staleSlot索引以外，没有任何的stale entry，那么slotToExpunge肯定没有变化，还是等于初始值staleSlot。
			// 理解到以上两点，就基本理解到replaceStaleEntry函数的逻辑了。对了，我们先把staleSlot所在的run分成两部分，staleSlot之前的部分，和staleSlot之后的部分。
			
			// 向前的连续段中，寻找最靠前的stale entry的索引
			int slotToExpunge = staleSlot; //slotToExpunge作为清理stale的起点
			
			// 向前寻找别的stale entry的索引
			// 直到向前到达了第一个为null的entry
			// 在for (int i = prevIndex(staleSlot, len);循环里，遍历run里staleSlot之前的部分，并最终将slotToExpunge停留在最靠前的stale entry的索引。
			// 当然，如果遍历过程中，没有发现stale entry，slotToExpunge不变。
			for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len))
				if (e.get() == null)
					slotToExpunge = i; //这个索引可能多次被替换。
			//即使向前找到了多个stale entry，只保留最靠前的那个的索引
            //循环结束，slotToExpunge要么不变，要么向前移动了

			// 向后的连续段中，寻找最靠后的stale entry的索引。
            // 当连续段结束，或者找到相同key时，循环结束
			// 直到向后到达了第一个为null的entry
			
			// 显然，在这个循环里，slotToExpunge只能移动一次，因为要保持“它的值为 staleSlot所在的run里，最前面的stale entry的所在索引”。
			for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
				ThreadLocal<?> k = e.get();

				// 如果找到key，则需要将其与旧条目进行交换，以保持哈希表的顺序。
				// 然后，可以将新过期的槽或上面遇到的任何其他过期槽发送到expungeStaleEntry，以删除或重新散列运行中的所有其他条目。
				// 如果找到了key，循环会结束。
				if (k == key) {
					// 如果当前循环发现了key，先把key所在entry更新value，然后交换i下标和staleSlot下标的entry，
					// 所以，最终效果还是“传入的key和value塞到staleSlot所在的下标上去”。并且不用担心交换后i 下标的stale entry，因为slotToExpunge肯定比 当前的i 小，最后一定会清理到的。
					// 注意，这里同样有slotToExpunge == staleSlot，解释同上，总之slotToExpunge只能移动一次。
					// 最后，来一套cleanSomeSlots(expungeStaleEntry(slotToExpunge), len)操作。
					e.value = value;//先将value，设置为找到的key所在的entry

					tab[i] = tab[staleSlot];//交换staleSlot和i索引的entry
					tab[staleSlot] = e;

					// 如果相等，说明staleSlot之前的连续段中，没有stale entry。
                    // 这里有两种情况，如果不同，可能是slotToExpunge向前移动了，
                    // 此时i肯定在slotToExpunge后面，执行slotToExpunge = i，再
                    // 执行expungeStaleEntry将会漏掉stale entry。
                    // 
                    // 如果不同，还可能是slotToExpunge向后移动了，只能是for循环外
                    // 的if分支执行的，此时slotToExpunge已经停留在staleSlot之后的
                    // 第一个stale entry上了，而现在的i肯定比slotToExpunge小，所以
                    // 不能再往后移动，不然执行expungeStaleEntry将会漏掉stale entry。
					if (slotToExpunge == staleSlot)
						slotToExpunge = i;
					cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
					return;
				}

				// 如果当前循环没有发现key，那么执行if (k == null && slotToExpunge == staleSlot)分支，前者条件成立，说明当前循环的是个stale entry；
				// 后者条件成立，说明run里staleSlot之前的部分，没有发现stale entry，且说明之前的循环过程中也没有发现stale entry，所以slotToExpunge保持了不变。
				// 如果二者都成立，说明slotToExpunge可以往后移动，因为要保持“它的值为 staleSlot所在的run里，最前面的stale entry的所在索引”。
				if (k == null && slotToExpunge == staleSlot)
					slotToExpunge = i;
				 //总之，slotToExpunge要么停留之前的最靠前的stale entry上，
                //要么停留在之后的第一个stale entry上。
			}

			//运行到这里，说明staleSlot向后的连续段中，没有找到key
			
			// 如果第二个循环也正常退出，继续执行了，说明在staleSlot所在的run里确实没有这个key。那么先执行“传入的key和value塞到staleSlot所在的下标上去”。
			// 当slotToExpunge不等于staleSlot，说明这个run里确实有stale entry，然后来一套cleanSomeSlots(expungeStaleEntry(slotToExpunge), len)操作。

            // 效果和上面其实一样，还是value设置在了staleSlot位置的entry里
            // 只不过上面先设置到别处，再交换过来
			tab[staleSlot].value = null;
			tab[staleSlot] = new Entry(key, value);

			// 正如上面分析，如果二者相等，说明向前向后的连续段中，都没有发现stale entry
            // 也就不需要执行清理操作了
			if (slotToExpunge != staleSlot)
				cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
		}

		/**
		 * 通过重新哈希位于staleSlot和下一个空槽之间的任何可能碰撞的条目来删除陈旧的条目。
		 * 这也将删除在末尾为null之前遇到的任何其他陈旧条目。SeeKnuth, 6.4节
		 * 
		 * 此方法从staleSlot索引开始，一直到循环开始前就为null的entry为止。
         * 过程中，如果遇到entry的key为null，执行清空操作；
         * 如果遇到entry的key因冲突而本不应该在当前位置，也清空当前位置，再从新为其找新位置
         * （可能找到离取模下标更近的位置）。
         * 
         * expungeStaleEntry函数，看名字就知道是用来清理stale entry的。而且get、set、remove、resize都可能调用到它，实际上它也确实是用来处理stale entry的主要函数。
         * 循环从来向后搜索连续段，当遇到null entry时（是指循环开始前就为null的entry），停止。
         * 每次循环中，遇到stale entry，清空它。
         * 每次循环中，遇到取模下标不是其实际下标的entry，为其rehash，以使得它移动到更靠近取模下标的位置上去。
		 *
		 * @param staleSlot index of slot known to have null key
		 * @return the index of the next null slot after staleSlot (all between
		 *         staleSlot and this slot will have been checked for expunging).
		 */
		private int expungeStaleEntry(int staleSlot) {			
			Entry[] tab = table;
			int len = tab.length;

			// staleSlot所在的entry包含null的key，所以清空
			tab[staleSlot].value = null;
			tab[staleSlot] = null;
			size--;

			// rehash直到我们遇到null
			Entry e;
			int i;
			// 循环会一直进行，直到通过nextIndex找到了第一个为null的entry
			for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
				ThreadLocal<?> k = e.get();
				if (k == null) {//如果又是一个staleSlot，也执行清空操作
					e.value = null;
					tab[i] = null;
					size--;
				} else {//key不为null
					int h = k.threadLocalHashCode & (len - 1);//得到k的取模下标
					if (h != i) {//如果不相等，说明k是因为冲突，才会放到i位置。而且，不考虑环形数组的话，h肯定比i小
						tab[i] = null;

						// 与Knuth 6.4算法R不同，我们必须扫描到null，因为多个条目可能已经失效。
						while (tab[h] != null)//再从h出发（不冲突的话，k就应该放到h位置），找到不冲突的位置
							h = nextIndex(h, len);
						//当退出时，h位置是空的
						tab[h] = e;//此时再把e赋值为h位置。当然也有可能，最终新的h还是等于i
					}
				}
			}
			return i;
		}

		/**
		 * 启发式地扫描一些单元格，寻找陈旧的条目。 当添加了一个新元素或删除了另一个过时的元素时，就会调用这个函数。
		 * 它执行等数的扫描，作为不扫描(快速但保留垃圾)和与元素数量成比例的扫描之间的平衡， 这将发现所有垃圾，但会导致一些插入花费O(n)时间。
		 * 
		 * cleanSomeSlots函数启发式地扫描并清空stale entry，其实启发是指扫描次数不一定是多少次。当别的函数调用到该函数时，参数n要么为个数，要么为容量。
		 *
		 * @param i a position known NOT to hold a stale entry. The scan starts at the
		 *          element after i.
		 *
		 * @param n scan control: 用来控制扫描的次数。次数可为log2(n)次，但如果扫描到
         * 										   stale entry，那么不管已扫描次数，再扫描log2(容量)次。
		 *
		 * @return true if any stale entries have been removed.
		 */
		private boolean cleanSomeSlots(int i, int n) {
			boolean removed = false;
			Entry[] tab = table;
			int len = tab.length;
			do {
				i = nextIndex(i, len);
				Entry e = tab[i];
				if (e != null && e.get() == null) {//检测到i位置的entry是一个stale entry
					n = len;//更新n为容量，接下来至少又得循环log2(容量)次
					removed = true;
					// 如果循环中发现了一次stale entry，那么不管之前执行了多少次循环，之后也至少执行log2(n)（n会更新为容量）。
					// 由于expungeStaleEntry的执行，i 可能会跳跃到 i 之后连续段的第一个null entry，然后下一次循环i 再移动。
					i = expungeStaleEntry(i);//返回i之后第一个为null的entry的索引，使得i跳跃
				}
			} while ((n >>>= 1) != 0);//n无符号右移，只是用来控制循环次数
			return removed;
		}

		/**
		 * 重新包装和/或调整表的大小。 首先扫描整个表，删除陈旧的条目。如果这还不足以缩小表的大小，那么将表的大小翻倍。
		 */
		private void rehash() {
			expungeStaleEntries();

			// 阈值本是2/3的容量，这里运算后，>=右边是等于1/2容量
            // 所以降低了阈值来判断是否需要resize
			if (size >= threshold - threshold / 4)
				resize();
		}

		/**
		 * 把表的容量翻倍。
		 */
		private void resize() {
			Entry[] oldTab = table;
			int oldLen = oldTab.length;
			int newLen = oldLen * 2;
			Entry[] newTab = new Entry[newLen];
			int count = 0;

			for (int j = 0; j < oldLen; ++j) {
				Entry e = oldTab[j];
				if (e != null) {
					ThreadLocal<?> k = e.get();
					if (k == null) {
						e.value = null; //清空stale entry
					} else {
						int h = k.threadLocalHashCode & (newLen - 1);
						while (newTab[h] != null)//开放寻址，找到最终位置
							h = nextIndex(h, newLen);
						newTab[h] = e;//赋值给最终位置
						count++;
					}
				}
			}

			setThreshold(newLen);
			size = count;
			table = newTab;
		}

		/**
		 * 删除表中所有陈旧的条目。
		 */
		private void expungeStaleEntries() {
			Entry[] tab = table;
			int len = tab.length;
			for (int j = 0; j < len; j++) {
				Entry e = tab[j];
				if (e != null && e.get() == null)
					// 或者你以为可以j = expungeStaleEntry(j),毕竟expungeStaleEntry会清理之后连续段的stale。
                    // 但是这样可能使得j直接跳回0，或者0之后的附近索引，然后造成再一次的循环。
					expungeStaleEntry(j);
			}
		}
	}
}
